/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						 combat_path_finder_base.cpp

	$Header: /heroes4/combat_path_finder_base.cpp $

	$NoKeywords: $

 ************************************************************************/
// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "combat_path_finder_base.h"

#include "combat_footprint.h"
#include "battlefield.h"
#include "direction.h"
#include "enum_operations.h"
#include "obstacle_type.h"
#include "stationary_combat_object.h"

// ---------------------------------------------------------------
// map of path data, movement costs, and passability for a given footprint size
// ---------------------------------------------------------------
t_combat_path_map::t_combat_path_map( int size ) 
{
	initialize( size, k_battlefield_cell_height, 
		        k_battlefield_logical_view_size );
	m_footprint_size = 0;
}


// ---------------------------------------------------------------
// map of path data, movement costs, and passability for a given footprint size
// ---------------------------------------------------------------
void t_combat_path_map::init_map( t_battlefield const& battlefield,
								  t_combat_path_blockage_map const& map, 
								  t_combat_footprint const& footprint )
{
	// clear array
	t_map_point_2d			point;
	int						row_end;
	t_combat_path_data*		ptr;
	int						footprint_size = footprint.get_size();
	t_combat_path_blockage  state;

	point.row = get_size();
	m_footprint_size = footprint_size;
	while (point.row--)
	{
		point.column = get_row_start( point.row );
		row_end = get_row_end( point.row );
		ptr = &get( point );
		memset( ptr, 0, get_row_size( point.row ) * sizeof( t_combat_path_data ));
		while (point.column < row_end)
		{
			ptr->off_map = battlefield.off_map( footprint_size, point );
			if (ptr->off_map)
				ptr->blocked = true;
			else
			{
				state = map.can_place( point, footprint );
				ptr->blocked = state.blocked;
				ptr->is_tower = state.in_tower;
				ptr->has_wall = state.has_wall;
				ptr->forbidden = state.forbidden;
			}
			ptr++;
			point.column++;
		}
	}
}

// ---------------------------------------------------------------
// map of path data, movement costs, and passability for a given footprint size
// mark an area as obstructed based on its position and size
// ---------------------------------------------------------------
void t_combat_path_map::mark_obstacle( t_combat_object_base const&   object,
									   t_combat_path_blockage const& state )
{
	int	size = object.get_footprint_size();

	if (size < 1)
		return;

	t_combat_creature const*	creature;
	t_map_point_2d				position = object.get_cell_position();

	creature = dynamic_cast<t_combat_creature const*>( &object );

	if (creature != 0 && creature->is_in_tower())
	{
		t_stationary_combat_object const* tower = creature->get_tower();

		size = tower->get_footprint_size();
		position = tower->get_cell_position();
	}


	t_combat_footprint const& footprint = get_footprint_overlap( size, m_footprint_size );
	int const*				  ptr = footprint.get();
	t_combat_path_data*       cell;
	t_map_point_2d			  offset;
	t_map_point_2d			  point;

	assert( footprint.get_size() == m_footprint_size + size - 1 );
	for (offset.row = -m_footprint_size + 1; offset.row < size; ++offset.row)
	{
		for (offset.column = -m_footprint_size + 1; offset.column < size; ++offset.column)
		{
			if (*(ptr++) == 0)
				continue;
			point = position + offset;
			if (!is_valid( point ))
				continue;
			cell = &get( point );
			if (state.in_tower)
				cell->is_tower = true;
			if (state.blocked)
				cell->blocked = true;
			if (state.has_wall)
				cell->has_wall = true;
		}
	}
}

// ---------------------------------------------------------------
// class to find paths for combat map
// ---------------------------------------------------------------
t_combat_path_finder_base::t_combat_path_finder_base( int size )
						 : m_data( size )
{
	m_initialized = false;
}

// ---------------------------------------------------------------
// class to find paths for combat map
// ---------------------------------------------------------------
void t_combat_path_finder_base::push_first_point( t_map_point_2d const& cell )
{
	t_combat_path_point start( cell );

	start.off_map = false;
	start.forbidden = false;
	start.entry_cost = 100;
	start.move_cost = 0;
	start.visited = true;
	start.reachable = true;
	start.flight_cost = 0;
	start.nearest_point = start;
	start.blocked = false;
	start.last_point.row = -1;
	start.last_point.column = -1;
	start.is_tower = false;
	start.has_wall = false;
	start.attackable = false;
	start.attack_distance = 0;
	m_open_points.push( start );
	// set initial point
	m_data.get( start ) = start;
}

// ---------------------------------------------------------------
// class to find paths for combat map
// ---------------------------------------------------------------

namespace
{
// ---------------------------------------------------------------
// function object to compare two combat path points
// ---------------------------------------------------------------
	class t_compare_move_cost
	{
	public:
		bool operator()( t_combat_path_point const& left, 
		                 t_combat_path_point const& right ) const
		{
			return left.move_cost > right.move_cost;
		}
	};
}; // unnamed namespace

// ---------------------------------------------------------------
// class to find paths for combat map
// ---------------------------------------------------------------
void t_combat_path_finder_base::push( t_combat_path_point const& point )
{
	t_combat_path_data& old_point = m_data.get( t_level_map_point_2d(point, 0) );

	if (old_point.visited && old_point.move_cost <= point.move_cost)
		return;

	m_open_points.push( point );
	old_point = point;
}

// ---------------------------------------------------------------
// class to find paths for combat map
// find best path to make any part of army touch square, not just upper
// corner.
// ---------------------------------------------------------------
void t_combat_path_finder_base::mark_reachable_points( t_combat_footprint const& footprint )
{
	// clear array
	t_map_point_2d			  point;
	int						  end;
	t_combat_path_data const* current_point;
	int                       new_distance;
	int                       old_distance;
	t_combat_path_data*		  new_point_data;
	int                       footprint_size = footprint.get_size();
	t_map_point_2d            offset;
	t_map_point_2d            new_point;
	int const*				  ptr;

	point.row = m_data.get_size();
	while (point.row--)
	{
		point.column = m_data.get_row_start( point.row );
		end = m_data.get_row_end( point.row );
		for (; point.column < end; point.column++)
		{
			current_point = &m_data.get( point );
			if (!current_point->visited || current_point->blocked)
				continue;

			new_distance = current_point->move_cost;
			ptr = footprint.get();
			for (offset.row = 0; offset.row < footprint_size; offset.row++)
			{
				offset.column = 0;
				for (offset.column = 0; offset.column < footprint_size; offset.column++)
				{
					if (!(*(ptr++)))
						continue;
					new_point = point + offset;
					new_point_data = &m_data.get( new_point );
					if (new_point_data->reachable)
					{
						old_distance = m_data.get( new_point_data->nearest_point ).move_cost;
						if (new_distance >= old_distance)
							continue;
					}
					new_point_data->nearest_point = point;
					new_point_data->reachable = true;
				}
			}
		}
	}
}


// ---------------------------------------------------------------
// class to find paths for combat map
// ---------------------------------------------------------------
bool t_combat_path_finder_base::get_path( t_map_point_2d point, t_combat_path& path )
{
	generate_paths();
	path.clear();

	t_combat_path_data data = m_data.get( point );

	if ( !data.visited )
		return false;
	while (data.last_point.column >= 0)
	{
		path.push_back( t_combat_path_point( point, data ) );
		point = data.last_point;
		assert( data.move_cost >= m_data.get( point ).move_cost );
		data = m_data.get( point );
	}
	return path.size() > 0;
}

// ---------------------------------------------------------------
// mark all permanent objects on blockage map
// ---------------------------------------------------------------
void t_combat_path_blockage_map::mark_obstacles( t_battlefield& battlefield )
{
	t_combat_object_const_iterator  index = battlefield.objects_begin();
	t_combat_object_const_iterator  end = battlefield.objects_end();
	t_abstract_combat_object const* object;
	t_combat_path_blockage			blockage;

	blockage.blocked = true;
	blockage.in_tower = false;
	blockage.has_wall = false;

	// mark all normal obstacles
	for (; index != end; index++)
	{
		object = index->get();
		if (!object->blocks_movement())
			continue;
		if (!object->is_permanent())
			continue;
		mark( object->get_cell_position(), object->get_footprint(), blockage );
	}

	// mark castle walls as being walls
	t_combat_path_blockage				tower_value;
	t_combat_path_blockage				wall_value;
	t_stationary_combat_object const*	wall_object;
	t_stationary_combat_object_list::iterator	wall_index;
	t_stationary_combat_object_list::iterator	wall_end;

	wall_index = battlefield.castle_begin();
	wall_end = battlefield.castle_end();
	tower_value.blocked = false;
	tower_value.in_tower = true;
	tower_value.has_wall = false;
	wall_value.blocked = true;
	wall_value.in_tower = false;
	wall_value.has_wall = true;
	for (; wall_index != wall_end; wall_index++)
	{
		// is this castle piece a tower?
		wall_object = wall_index->get();
		switch (wall_object->get_obstacle_type())
		{
			case k_obstacle_castle_wall:
				mark( wall_object->get_cell_position(), wall_object->get_footprint(),
				      wall_value );
				break;

			case k_obstacle_castle_tower:
				// mark all squares in the tower as passable and in a tower
				mark( wall_object->get_cell_position(), wall_object->get_footprint(),
					  tower_value );
				break;
		}
	}

	// mark areas forbidden - either in upper area, or impassable on preset map
	t_map_point_2d  point;
	int				end_column;
	t_combat_path_blockage* ptr;

	point.row = get_size();
	while (point.row--)
	{
		point.column = get_row_start( point.row );
		end_column = get_row_end( point.row );
		for (; point.column < end_column; point.column++)
		{
			if (battlefield.get_cell( point ).is_forbidden() )
			{
				ptr = &get(point);
				ptr->forbidden = true;
				ptr->blocked = true;
			}
		}
	}
}


// ---------------------------------------------------------------
// determine result of trying to place object in a spot
// ---------------------------------------------------------------
t_combat_path_blockage 
	t_combat_path_blockage_map::can_place( t_map_point_2d const&		point,
										   t_combat_footprint const&	footprint ) const
{
	int                       footprint_size = footprint.get_size();
	t_map_point_2d            offset;
	t_map_point_2d            new_point;
	int const*				  ptr = footprint.get();
	t_combat_path_blockage    result;
	t_combat_path_blockage const* data;

	result.blocked = false;
	result.in_tower = false;
	result.has_wall = false;
	result.forbidden = false;
	for (offset.row = 0; offset.row < footprint_size; offset.row++)
	{
		for (offset.column = 0; offset.column < footprint_size; offset.column++)
		{
			if (!(*(ptr++)))
				continue;
			new_point = point + offset;
			if (!is_valid( new_point ))
			{
				result.blocked = true;
				result.forbidden = true;
				return result;
			}
			data = &get( new_point );
			if (data->blocked)
				result.blocked = true;
			if (data->in_tower)
				result.in_tower = true;
			if (data->has_wall)
				result.has_wall = true;
			if (data->forbidden)
				result.forbidden = true;
		}
	}
	return result;
}

// ---------------------------------------------------------------
// mark an area in the blockage map
// ---------------------------------------------------------------
void t_combat_path_blockage_map::mark( t_map_point_2d const&		point,
									   t_combat_footprint const&	footprint,
									   t_combat_path_blockage		value )
{
	int				footprint_size;
	int const*		ptr;
	t_map_point_2d  new_point;
	t_map_rect_2d   rect;

	ptr = footprint.get();
	footprint_size = footprint.get_size();
	rect.top_left = point;
	rect.bottom_right.row = point.row + footprint_size;
	rect.bottom_right.column = point.column + footprint_size;
	for (new_point.row = rect.top(); new_point.row < rect.bottom(); new_point.row++)
	{
		for (new_point.column = rect.left(); new_point.column < rect.right(); new_point.column++)
		{
			if (!(*(ptr++)))
				continue;
			if (is_valid( new_point ))
				get( new_point ) = value;
		}
	}
}
